package _18_剑指OfferII;

import java.util.Arrays;

public class _106_剑指OfferII二分图 {

    private static final int UN_COLOR = -1;

    private static final int RED = 0;

    private static final int GREEN = 1;

    int[] colors;

    boolean valid;

    // 染色确定，是否为二分图
    public boolean isBipartite(int[][] graph) {
        int len = graph.length;
        this.colors = new int[len];
        valid = true;
        // 初始化数据
        Arrays.fill(colors, UN_COLOR);

        for (int i = 0; i < len && valid; ++i) {
            if (colors[i] == UN_COLOR) {
                // 深度遍历元素
                dfs(graph, i, RED);
            }
        }
        return valid;
    }

    private void dfs(int[][] graph, int i, int color) {
        colors[i] = color;
        int nextColor = color == RED? GREEN: RED;

        for (int index: graph[i]) {
            if (colors[index] == UN_COLOR) {
                dfs(graph, index, nextColor);
                if (!valid) return;
            } else if (colors[index] != nextColor) {
                valid = false;
                return;
            }
        }
    }

}
